#include "TK.h"

Node* amalgamate(Node* head1,Node* head2){

	Node* newhead;
	Node* p1;
	Node* p2;	

	if(head1 == NULL)
	return head2;
	if(head2 == NULL)
	return head1;	

	if(head1->data >= head2->data)
	{
		 newhead = head2;
                 p1 = head1;
		 p2 = head2->next;
	}
	else
	{
		newhead = head1;
		p1 = head1->next;
		p2 = head2;
	}

	Node* move = newhead;

	while(p1&&p2)
	{
		if(p1->data >= p2->data)
		{
			move->next = p2;
			move = p2;
			p2 = p2->next;
			
		}	
		else
		{
			move->next = p1;
			move = p1;
			p1 = p1->next; 
		}
	}

	if(p1 == NULL)
		move->next = p2;
	else if(p2 == NULL)
		move->next = p1;

	return newhead;
}

Node* erase(Node* head,char n){
	Node* tool = head;
	Node* probe = head;
	while(n-- != '0')//n is a char , cannot directly type "while(n--)"
	tool = tool->next;
	while(tool != NULL && tool->next != NULL)
	{
		tool = tool->next;
		probe = probe->next;
	}  
	probe->next = probe->next->next;
	return head;
}

Node* middle(Node* head){
	if(head == NULL || head->next == NULL)
	return head;
	Node* slow = head;
	Node* fast = head;
	while(fast->next != NULL && fast->next->next != NULL)
	{
		slow = slow->next;
		fast = fast->next->next;
		if(fast->next == NULL)
		break;
	}
	return slow;
	
}
